/*********************************************************************************************************
 *  ------------------------------------------------------------------------------------------------------
 *  file description
 *  ------------------------------------------------------------------------------------------------------
 *         \file  deque.c
 *        \brief  This is a general-purpose C language deque module, with circular mode and common data structure
 *       \author  Lamdonn
 *        \email  Lamdonn@163.com
 *      \version  1.1.0
 *      \license  GPL2
 *    \copyright  Copyright (C) 2023 Lamdonn.
 ********************************************************************************************************/
#include "vlib.h"
#include <string.h>
#include <stdlib.h>

#define IDENT                           (4)

/* array at */
#define at(base, size, index)           (((unsigned char *)base)+(index)*(size))

int deque_init(deque_t deque, void* array, int dsize, int capacity)
{
    /* validity check */
    if (!deque) return 0;
    if (!array) return 0;
    if (dsize <= 0) return 0;
    if (capacity <= 0) return 0;

    /* assign parameters */
    deque->parent.ident = IDENT;
    deque->parent.base = array;
    deque->parent.dsize = dsize;
    deque->parent.size = 0;
    deque->capacity = capacity;
    deque->mode = DEQUE_MODE_DEFAULT;
    deque->tail = 0;
    deque->head = 0;

    return 1;
}

void deque_deinit(deque_t deque)
{
    /* validity check */
    if (!deque) return;

    deque->tail = 0;
    deque->head = 0;
    deque->parent.size = 0;
    deque->mode = DEQUE_MODE_DEFAULT;
    deque->capacity = 0;
    deque->parent.dsize = 0;
    deque->parent.base = NULL;
}

deque_t deque_create(int dsize, int capacity)
{
    deque_t new_deque = NULL;
    void* base = NULL;

    if (dsize <= 0 || capacity <= 0)
    {
        return NULL;
    }

    /* allocate deque */
    new_deque = (deque_t )vlib_malloc(sizeof(DEQUE));
    if (new_deque == NULL)
    {
        return NULL;
    }

    /* allocate space to deque */
    base = vlib_malloc(dsize * capacity);
    if (base == NULL)
    {
        vlib_free(new_deque);
        return NULL;
    }

    /* init deque */
    if (deque_init(new_deque, base, dsize, capacity) != 1)
    {
        vlib_free(base);
        vlib_free(new_deque);
        return NULL;
    }

    new_deque->mode |= DEQUE_MODE_RESIZE;

    return new_deque;
}

void deque_delete(deque_t deque)
{
    /* validity check */
    if (!deque) return;

    vlib_free(deque->parent.base);
    deque_deinit(deque);
    vlib_free(deque);
}

int deque_empty(deque_t deque)
{
    /* validity check */
    if (!deque) return 1;
    return deque->parent.size == 0 ? 1 : 0;
}

int deque_full(deque_t deque)
{
    /* validity check */
    if (!deque) return 0;

    return (deque->parent.size == deque->capacity) ? 1 : 0;
}

int deque_size(deque_t deque)
{
    /* validity check */
    if (!deque) return 0;
    return deque->parent.size;
}

int deque_push_front(deque_t deque, void* data)
{
    /* validity check */
    if (!deque) return 0;

    /* check permissions */
    if ((deque->mode & DEQUE_MODE_LMT_PUSH) != 0)
    {
        return 0;
    }

    if (deque_full(deque))
    {
        if ((deque->mode & DEQUE_MODE_OVERWRITE) != 0)
        {
            deque->head = (deque->head + deque->capacity - 1) % deque->capacity;
            deque->tail = (deque->tail + deque->capacity - 1) % deque->capacity;
            if (data != NULL) memcpy(at(deque->parent.base, deque->parent.dsize, deque->head), data, deque->parent.dsize);
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        /* copy this item to the deque */
        deque->head = (deque->head + deque->capacity - 1) % deque->capacity;
        if (data != NULL) memcpy(at(deque->parent.base, deque->parent.dsize, deque->head), data, deque->parent.dsize);
        deque->parent.size++;
        return 1;
    }

    return 1;
}

int deque_push_back(deque_t deque, void* data)
{
    /* validity check */
    if (!deque) return 0;

    /* check permissions */
    if ((deque->mode & DEQUE_MODE_LMT_PUSH) != 0)
    {
        return 0;
    }

    if (deque_full(deque))
    {
        if ((deque->mode & DEQUE_MODE_OVERWRITE) != 0)
        {
            if (data != NULL) memcpy(at(deque->parent.base, deque->parent.dsize, deque->tail), data, deque->parent.dsize);
            deque->tail++;
            deque->tail %= deque->capacity;
            deque->head++;
            deque->head %= deque->capacity;
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        /* copy this item to the deque */
        if (data != NULL) memcpy(at(deque->parent.base, deque->parent.dsize, deque->tail), data, deque->parent.dsize);
        deque->tail++;
        deque->tail %= deque->capacity;                    /* after the deque counter exceeds the maximum value, start from 0 */
        deque->parent.size++;
        return 1;
    }

    return 1;
}

int deque_pop_front(deque_t deque, void* data)
{
    /* validity check */
    if (!deque) return 0;

    /* check mode */
    if ((deque->mode & DEQUE_MODE_LMT_POP) != 0)
    {
        return 0;
    }

    if (deque_empty(deque))
    {
        return 0;
    }
    else
    {
        /* extract data from pairs of columns */
        if (data != NULL) memcpy(data, at(deque->parent.base, deque->parent.dsize, deque->head), deque->parent.dsize);
        if ((deque->mode & DEQUE_MODE_POP_RESET) != 0)
        {
            memset(at(deque->parent.base, deque->parent.dsize, deque->head), 0, deque->parent.dsize);
        }
        if ((deque->mode & DEQUE_MODE_POP_HOLD) == 0)
        {
            deque->head++;
            deque->head %= deque->capacity;        /* index of loop header */
            deque->parent.size--;
        }
        return 1;
    }
}

int deque_pop_back(deque_t deque, void* data)
{
    int t_back = 0;

    /* validity check */
    if (!deque) return 0;

    /* check mode */
    if ((deque->mode & DEQUE_MODE_LMT_POP) != 0)
    {
        return 0;
    }

    if (deque_empty(deque))
    {
        return 0;
    }
    else
    {
        t_back = (deque->tail + deque->capacity - 1) % deque->capacity;
        /* extract data from pairs of columns */
        if (data != NULL) memcpy(data, at(deque->parent.base, deque->parent.dsize, t_back), deque->parent.dsize);
        if ((deque->mode & DEQUE_MODE_POP_RESET) != 0)
        {
            memset(at(deque->parent.base, deque->parent.dsize, t_back), 0, deque->parent.dsize);
        }
        if ((deque->mode & DEQUE_MODE_POP_HOLD) == 0)
        {
            deque->parent.size--;
            deque->tail = t_back;
        }
        return 1;
    }
}

void deque_clear(deque_t deque)
{
    /* validity check */
    if (!deque) return;

    deque->tail = 0;
    deque->head = 0;
    deque->parent.size = 0;
}

void* deque_data(deque_t deque, int index, int orgin)
{
    void* p_ret = NULL;
    int t_index = 0;

    /* validity check */
    if (!deque) return NULL;

    if (index >= deque->parent.size)
    {
        index = deque->parent.size - 1;
    }
    else if (index < 0)
    {
        index = 0;
    }

    if (orgin == DEQUE_ORGIN_FRONT) /* head */
    {
        t_index = (deque->head + index) % (deque->capacity);
    }
    else /* tail */
    {
        t_index = (deque->tail + deque->capacity - index - 1) % (deque->capacity);
    }

    p_ret = at(deque->parent.base, deque->parent.dsize, t_index);

    return p_ret;
}

/** swap_item
 *  \brief swap two data
 *  \param[in] data0: address of data0
 *  \param[in] data1: address of data1
 *  \param[in] dsize: size of data
 *  \return none
 */
static void swap_item(void* data0, void* data1, int dsize)
{
    unsigned char temp = 0;
    int i = 0;

    for (i = 0; i < dsize; i++)
    {
        temp = ((unsigned char *)data0)[i];
        ((unsigned char *)data0)[i] = ((unsigned char *)data1)[i];
        ((unsigned char *)data1)[i] = temp;
    }
}

int deque_insert(deque_t deque, int index, void* data, int orgin)
{
    int i = 0;
    int move_count = 0;
    int temp_orgin = orgin;

    /* validity check */
    if (!deque) return 0;

    if (index > deque->parent.size || index < 0)
    {
        return 0;
    }

    if (deque_full(deque) == 1 && (deque->mode & DEQUE_MODE_OVERWRITE) == 0)
    {
        return 0;
    }

    if (orgin == DEQUE_ORGIN_FRONT)
    {
        if (index < deque->parent.size - index)
        {
            move_count = index;
            deque_push_front(deque, data);
            temp_orgin = DEQUE_ORGIN_FRONT;
        }
        else  
        {
            if (deque_full(deque) == 0)
            {
                move_count = deque->parent.size - index;
                deque_push_back(deque, data);
            }
            else  
            {
                move_count = deque->parent.size - index - 1;
                memcpy(deque_data(deque, 0, DEQUE_ORGIN_BACK), data, deque->parent.dsize);
            }
            temp_orgin = DEQUE_ORGIN_BACK;
        }
    }
    else if (orgin ==  DEQUE_ORGIN_BACK)
    {
        if (index < deque->parent.size - index)
        {
            move_count = index;
            deque_push_back(deque, data);
            temp_orgin = DEQUE_ORGIN_BACK;
        }
        else  
        {
            if (deque_full(deque) == 0)
            {
                move_count = deque->parent.size - index;
                deque_push_front(deque, data);
            }
            else  
            {
                move_count = deque->parent.size - index - 1;
                memcpy(deque_data(deque, 0, DEQUE_ORGIN_FRONT), data, deque->parent.dsize);
            }
            temp_orgin = DEQUE_ORGIN_FRONT;
        }
    }
    else  
    {
        return 0;
    }

    /* adjust insertion position */
    for (i = 0; i < move_count; i++)
    {
        swap_item(deque_data(deque, i, temp_orgin), deque_data(deque, i + 1, temp_orgin), deque->parent.dsize);
    }

    return 1;
}

int deque_erase(deque_t deque, int begin, int end, int orgin)
{
    int i = 0;
    int move_count = 0;
    int move_bias = 0;
    int temp_orgin = orgin;

    /* validity check */
    if (!deque) return 0;

    if (begin >= deque->parent.size)
    {
        begin = deque->parent.size - 1;
    }
    else if (begin < 0)
    {
        begin = 0;
    }

    if (end >= deque->parent.size)
    {
        end = deque->parent.size - 1;
    }
    else if (end < 0)
    {
        end = 0;
    }

    if (begin > end)
    {
        return 0;
    }

    move_bias = end - begin + 1;
    if (orgin == DEQUE_ORGIN_FRONT)
    {
        if (begin < deque->parent.size - end)
        {
            move_count = begin;
            temp_orgin = DEQUE_ORGIN_FRONT;
        }
        else  
        {
            move_count = deque->parent.size - end - 1;
            temp_orgin = DEQUE_ORGIN_BACK;
        }
    }
    else if (orgin == DEQUE_ORGIN_BACK)
    {
        if (begin < deque->parent.size - end)
        {
            move_count = begin;
            temp_orgin = DEQUE_ORGIN_BACK;
        }
        else  
        {
            move_count = deque->parent.size - end - 1;
            temp_orgin = DEQUE_ORGIN_FRONT;
        }
    }
    else  
    {
        return 0;
    }

    /* move */
    for (i = move_count - 1; i >= 0; i--)
    {
        memcpy(deque_data(deque, i + move_bias, temp_orgin), deque_data(deque, i, temp_orgin), deque->parent.dsize);
    }

    /* pop */
    if (temp_orgin == DEQUE_ORGIN_FRONT)
    {
        for (i = 0; i < move_bias; i++)
        {
            deque_pop_front(deque, NULL);
        }
    }
    else 
    {
        for (i = 0; i < move_bias; i++)
        {
            deque_pop_back(deque, NULL);
        }
    }

    return 1;
}

int deque_read(deque_t deque, int index, void* data, int orgin)
{
    void* op_ptr = NULL;

    /* validity check */
    if (!deque) return 0;

    if (index >= deque->parent.size || index < 0)
    {
        return 0;
    }

    if (data == NULL)
    {
        return 0;
    }

    /* check mode */
    if ((deque->mode & DEQUE_MODE_READ) == 0)
    {
        return 0;
    }

    op_ptr = deque_data(deque, index, orgin);
    if (op_ptr == NULL)
    {
        return 0;
    }
    else 
    {
        memcpy(data, op_ptr, deque->parent.dsize);
    }

    return 1;
}

int deque_modify(deque_t deque, int index, void* data, int orgin)
{
    void* op_ptr = NULL;

    /* validity check */
    if (!deque) return 0;

    if (index >= deque->parent.size || index < 0)
    {
        return 0;
    }

    if (data == NULL)
    {
        return 0;
    }

    /* check mode */
    if ((deque->mode & DEQUE_MODE_MODIFY) == 0)
    {
        return 0;
    }

    op_ptr = deque_data(deque, index, orgin);
    if (op_ptr == NULL)
    {
        return 0;
    }
    else 
    {
        memcpy(op_ptr, data, deque->parent.dsize);
    }

    return 1;
}

int deque_capacity(deque_t deque)
{
    /* validity check */
    if (!deque) return 0;
    return deque->capacity;
}

int deque_alter_capacity(deque_t deque, int capacity)
{
    void* n_addr = NULL;

    /* validity check */
    if (!deque) return 0;

    if (capacity <= 0)
    {
        return 0;
    }

    /* check mode */
    if ((deque->mode & DEQUE_MODE_RESIZE) == 0)
    {
        return 0;
    }

    if (capacity < deque->capacity)
    {
        /* discard data */
        if (capacity < deque->parent.size)
        {
            if ((deque->mode & DEQUE_MODE_DROP_FRONT) != 0)
            {
                deque->head =  (deque->head + (deque->parent.size - capacity)) % deque->capacity;
            }
            else  
            {
                deque->tail = (deque->tail + deque->capacity - (deque->parent.size - capacity)) % deque->capacity;
                
            }

            deque->parent.size = capacity;
        }

        /* need move */
        deque->tail = (deque->tail==0?deque->capacity:deque->tail);
        if (deque->head < deque->tail)
        {
            memmove(at(deque->parent.base, deque->parent.dsize, 0), 
                    at(deque->parent.base, deque->parent.dsize, deque->head),
                    (deque->tail - deque->head) * deque->parent.dsize);
            deque->tail = (deque->tail + deque->capacity - deque->head) % deque->capacity;
            deque->head = 0;
        }
        else  
        {
            memmove(at(deque->parent.base, deque->parent.dsize, capacity - (deque->capacity - deque->head)), 
                    at(deque->parent.base, deque->parent.dsize, deque->head),
                    (deque->capacity - deque->head) * deque->parent.dsize);
            deque->head = (deque->head + deque->capacity - (deque->capacity - capacity)) % deque->capacity;
            deque->tail %= deque->capacity;
        }

        n_addr = vlib_realloc(deque->parent.base, capacity * deque->parent.dsize);
        
        deque->capacity = capacity;
    }
    else if (capacity > deque->capacity)
    {
        n_addr = vlib_realloc(deque->parent.base, capacity * deque->parent.dsize);
        if (n_addr == NULL)
        {
            return 0;
        }
        deque->parent.base = n_addr;

        /* need move */
        if ((deque->head > deque->tail) || 
            (deque_full(deque) == 1 && deque->head != 0))
        {
            memmove(at(deque->parent.base, deque->parent.dsize, deque->head + (capacity - deque->capacity)), 
                    at(deque->parent.base, deque->parent.dsize, deque->head),
                    (deque->capacity - deque->head) * deque->parent.dsize);
            deque->head += (capacity - deque->capacity);
        }
        else if (deque_full(deque) == 1 && deque->head == 0)
        {
            deque->tail += deque->capacity;
        }

        deque->capacity = capacity;
    }

    deque->head %= deque->capacity;
    deque->tail %= deque->capacity;
    
    return 1;
}

void deque_mode(deque_t deque, int mode, int set)
{
    /* validity check */
    if (!deque) return;

    if (set == DEQUE_SET_MODE)
    {
        deque->mode |= mode;
    }
    else if (set == DEQUE_RESET_MODE)
    {
        deque->mode &= (~mode);
    }
}

void* deque_iterator_begin(vobject_t object)
{
    if (!object) return NULL;
    return at(((deque_t)object)->parent.base, ((deque_t)object)->parent.dsize, ((deque_t)object)->head);
}

void* deque_iterator_end(vobject_t object)
{
    if (!object) return NULL;
    return at(((deque_t)object)->parent.base, ((deque_t)object)->parent.dsize, (((deque_t)object)->tail + ((deque_t)object)->capacity - 1) % ((deque_t)object)->capacity);
}

void* deque_iterator_move(vobject_t object, void *node, int step)
{
    char *temp = ((char *)node) + step * ((deque_t)object)->parent.dsize;
    if ((void *)temp < ((deque_t)object)->parent.base) temp += (((deque_t)object)->parent.dsize * ((deque_t)object)->capacity);
    else if ((unsigned char *)temp >= at(((deque_t)object)->parent.base, ((deque_t)object)->parent.dsize, ((deque_t)object)->capacity)) temp -= (((deque_t)object)->parent.dsize * ((deque_t)object)->capacity);
    return (void *)temp;
}

void deque_iterator_nfs(void *node, void **first, void **second)
{
    if (!node) return;
    if (first) *first = NULL;
    if (second) *second = node;
}
